package com.fr.lintcode;

/**
 * 递归，超时
*作者：furong
*日期：2017年2月20日
*时间：下午5:59:13
*/
public class Q534 {
    int total = 0;

    public int houseRobber2(int[] nums) {
        int lenth = nums.length;
        boolean[] hasRobbed = new boolean[lenth];
        rob(0, lenth, nums, hasRobbed, 0);
        return total;
    }

    private void rob(int i, int lenth, int[] num, boolean[] hasRobbed, int sum) {
        if (i >= lenth) {
            save(sum);
        } else {
            // 不能抢
            if (hasRobbed[(i - 1 + lenth) % lenth] || hasRobbed[(i + 1) % lenth]) {
                rob(i + 1, lenth, num, hasRobbed, sum);
            } else {
                // 能抢
                // 不抢
                rob(i + 1, lenth, num, hasRobbed, sum);
                // 抢
                sum += num[i];
                hasRobbed[i] = true;
                rob(i + 1, lenth, num, hasRobbed, sum);
                sum -= num[i];
                hasRobbed[i] = false;
            }
        }
    }

    private void save(int sum) {
        if (total <= sum) {
            total = sum;
        }
    }
}
